package com.wzp.algorithm.must;

import java.util.Arrays;

public class InsertSort {

    // 插入排序
    public static void insertSort(int[] array) {
        // 从数组的第二个元素开始循环将数组中的元素插入
        for (int i = 1; i < array.length; i++) {
            // 要插入的数据,设置数组中的第2个元素为第一次循环要插入的数据
            int insertVal = array[i];
            int index = i;
            while (index > 0 && insertVal < array[index - 1]) {
                // 如果要插入的元素小于第index个元素,就将第index个元素向后移动
                array[index] = array[index - 1];
                index--;
            }
            // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
            array[index] = insertVal;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{42, 19, 18, 35, 99, 12, 76};

//        insertSort(array);
        insertSort1(array);
        System.out.println("insertSort result:" + Arrays.toString(array));
    }

    public static void insertSort1(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int insertV = array[i];
            int index = i;
            while (index > 0 && insertV < array[i - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = insertV;
        }
    }


}
